//package LeetCodeHot100;
//
////前缀树结构
//class TrieNode {
//    //节点后续节点
//    TrieNode[] nexts;
//    //需要统计的指标
//    //通过该字符个数
//    int pass;
//    //以该字符结尾个数
//    int end;
//
//    public TrieNode() {
//        this.pass = 0;
//        this.end = 0;
//        //26代表这个节点后续最多有26条路，分别对应26个小写字母
//        nexts = new TrieNode[26];
//    }
//}
//
//public class Trie{
//    private TrieNode root;
//
//    public Trie() {
//        this.root = new TrieNode();
//    }
//
//    //前缀树字符搜索(word这个单词之前加入过几次) O(n)
//
//    public int search(String word) {
//        char[] chars = word.toCharArray();
//        TrieNode TrieNode = this.root;
//        int index = 0;
//        for (int i = 0; i < chars.length; i++) {
//            //确定下标
//            index = chars[i] - 'a';
//            if (TrieNode.nexts[index] == null) return 0;
//            //TrieNode指针指到下一个节点
//            TrieNode = TrieNode.nexts[index];
//        }
//        return TrieNode.end;
//    }
//
//
//    //前缀树字符插入 O(n)
//    public void insert(String word) {
//        char[] chars = word.toCharArray();
//        TrieNode TrieNode = this.root;
//        TrieNode.pass++;
//        int index = 0;
//        for (int i = 0; i < chars.length; i++) {
//            index = chars[i] - 'a';
//            if (TrieNode.nexts[index] == null) {
//                TrieNode.nexts[index] = new TrieNode();
//            }
//            TrieNode = TrieNode.nexts[index];
//            TrieNode.pass++;
//        }
//        TrieNode.end++;
//    }
//
//
//    //前缀树字符删除  O(n)
//    public void delete(String word) {
//        if (search(word) != 0) {
//            char[] chars = word.toCharArray();
//            TrieNode TrieNode = this.root;
//            TrieNode.pass--;
//            int index = 0;
//            for (int i = 0; i < chars.length; i++) {
//                index = chars[i] - 'a';
//                //从树的结构看，如果最终到达的是叶子节点，置空返回即可，不懂画图
//                if (--TrieNode.nexts[index].pass == 0) {
//                    TrieNode.nexts[index] = null;
//                    return;
//                }
//                TrieNode = TrieNode.nexts[index];
//                //TrieNode.pass-- ;在if里已经优化了，可以省略
//            }
//            TrieNode.end--;
//        }
//    }
//}
